package com.sicheng.蓝桥.练习题.dp;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/27 17:18
 */
public class dp_跳跃的小明 {
    /**
     * 问题描述
     * 　　有一条长为n的走廊，小明站在走廊的一端，每次可以跳过不超过p格，每格都有一个权值wi。
     * 　　小明要从一端跳到另一端，不能回跳，正好跳t次，请问他跳过的方格的权值和最大是多少？
     * 输入格式
     * 　　输入的第一行包含两个整数n, p, t，表示走廊的长度，小明每次跳跃的最长距离和小明跳的次数。
     * 　　接下来n个整数，表示走廊每个位置的权值。
     * 输出格式
     * 　　输出一个整数。表示小明跳过的方格的权值和的最大值。
     * 样例输入
     * 8 5 3
     * 3 4 -1 -100 1 8 7 6
     * 样例输出
     * 12
     * 数据规模和约定
     * 　　1<=n, p, t<=1000, -1000<=wi<=1000。
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int p = scanner.nextInt();
        int t = scanner.nextInt();

        int[] w = new int[n];
        long temp=0;
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
            temp+=w[i];
        }
        if (p == 1) {
            System.out.println(temp);
            return;
        }
        int[][] dp = new int[t + 1][n + 1];

        for (int[] ints : dp) {
            Arrays.fill(ints, Integer.MIN_VALUE >> 1);
        }
        dp[0][0] = 0;

        int res = Integer.MIN_VALUE;
        for (int i = 1; i < t; i++) {
            for (int j = i; j <= n && j < i * p + 1; j++) {
                for (int k = 1; k <= p && j - k >= 0; k++) {
                    dp[i][j] = Math.max(dp[i - 1][j - k] + w[j - 1], dp[i][j]);
                }
            }
        }
        for (int i = 0; i <= p && n - i >= 0; i++) {
            if (p > i) {
                res = Math.max(res, dp[t - 1][n - i]);
            }
        }
        System.out.println(res);
    }
}
